Mike từng là một tên tội phạm nhỏ, làm việc cho Vinnie vốn quen biết nhiều hơn. Chính Vinnie đã ra tay cứu giúp anh khi Mike còn là kẻ vô gia cư, mặc dù không có nhiều thông tin được tiết lộ về việc này.

Mọi việc bắt đầu từ lúc Mike đang tính chuyện rời khỏi Liberty City cùng với Vinnie và rửa tay gác kiếm khỏi quãng đời lầm lỗi ở chỗ mới, giống như San Fierro hoặc Vice City, nhưng Vinnie quyết định rằng họ nên tìm kiếm thêm một vài công việc từ ông chủ của họ là Mafia (dù không tiết lộ đây là gia đình Mafia nào; địa điểm của trò chơi trong niên biểu Grand Theft Auto cho thấy có thể đây chính là Forellis, hoặc nhiều khả năng là Leones), trước khi đi khỏi Liberty, để có thể thu thập thêm tiền bạc nhằm ổn định cuộc sống nơi khác.

Tuy nhiên, trong lần làm việc gần đây nhất sẽ đảm bảo cho họ đủ số tiền mơ ước, Vinnie thiệt mạng trong một vụ nổ bom xe, khiến toàn bộ số tiền mồ hôi nước mắt của họ bị thiêu hủy trong phút chốc. Mike từ lâu đã coi Vinnie giống như một người cha thứ hai, tức giận thề rằng sẽ trả thù và giết chết kẻ đã đặt bom, rồi lên đường tìm kiếm câu trả lời. Nhiệm vụ theo đuổi mối thù truyền kiếp của Mike dẫn đến việc anh tự tách mình ra khỏi giới mafia.

Mike trước tiên vào làm việc cho 8-Ball với lời khuyên anh nên đi kiếm Jonnie, một người pha chế rượu có mối liên hệ với bọn tội phạm trên toàn thành phố. Mike làm việc cho Jonnie với hy vọng khám phá ra sự thật, mặc dù vẫn khó chịu trước thói ngạo mạn của Jonnie. Cuối cùng, Mike phát hiện ra rằng Jonnie đã bị giết bởi vì anh sắp sửa lần ra được manh mối. Đồng thời, có người nhìn thấy Yardies đang chạy trốn khỏi quán bar của Jonnie và Mike đuổi theo bọn họ đến tận Đảo Staunton.

Mike tỏ ra nghi ngờ về tay trùm của Yardie, King Courtney phải chịu trách nhiệm và đưa hắn vào tầm ngắm. King Courtney phủ nhận những lời buộc tội cho rằng chính hắn cũng là người chịu trách nhiệm vì Jonnie nợ tiền của Yardies. Mike và King Courtney cùng nhau tìm ra sự thật, nhưng Mike tự nhận thấy là mình chưa tiếp cận được sự thật. King Courtney nói cho Mike biết kẻ chủ mưu chính là lãnh đạo của băng Colombia Cartel, Cisco. Sau khi Mike đối đầu với Cisco, mới làm sáng tỏ một điều là King Courtney chỉ đang lợi dụng anh mà thôi.

Mike quyết định làm việc cho Cisco để đổi lại lời hứa tìm ra ai là kẻ đứng đàng sau mọi thứ, và những thành tích phạm tội của Mike cũng thu hút sự chú ý của Asuka, người còn đứng ra giúp đỡ Mike tận tình. Trớ trêu thay, điều này có nghĩa là Mike kết thúc làm việc cho hai băng nhóm đang giao chiến lẫn nhau. Mike kết thúc mọi việc bằng cách giải cứu cô cháu gái bị bắt cóc của Asuka (điều mỉa mai cô này cũng chính là người bị Mike bắt cóc theo lệnh của Cisco).

Trong các màn sau cùng của trò chơi, Mike mới nhận ra Cisco đã bị ám sát và đuổi theo kẻ giết người. Đến phút cuối thì anh phát hiện ra rằng Vinnie đã thực sự ngụy trang cái chết của mình, cũng như kế hoạch tổng thể của ông ta; một mình rời khỏi thành phố và phần tiền của Mike, nhưng âm thầm theo dõi Mike khắp thành phố để ngăn cản anh tìm ra sự thật. Vinnie và các vệ sĩ của hắn cố gắng giết Mike, nhưng trong trận đấu súng tay đôi Mike đã bắn Vinnie bị thương và lớn tiếng cảnh báo rằng anh sẽ là mục tiêu của giới tội phạm ngầm vì sự giàu có của Mike, nhưng Mike đã kết liễu hắn từ đời nào rồi.

Trong vài nhiệm vụ tiếp theo, 8-Ball bị tống giam (bối cảnh trong vụ trốn thoát của nhân vật này trong đoạn phim mở đầu của Grand Theft Auto III'), và Mike biết rằng giờ mình là mục tiêu của Cartel. Mike tham gia một trận thư hùng với tay trùm Cartel và biết được rằng King Courtney hiện đang săn đuổi Mike vì sự giàu có của anh. Mike và nhóm Yakuza tấn công nơi ẩn náu của King Courtney, nhưng đám Yakuza đã bỏ chạy trước khi mở đầu cuộc tấn công. Trong màn đấu súng gay go, Mike vẫn nắm lấy phần thắng thuộc về mình và suýt nữa thì giết được King Courtney, nhưng bất ngờ bị gián đoạn bởi một cuộc đột kích của đám cảnh sát. Mike buộc phải chạy trốn trong khi King Courtney bỏ chạy ngay lập tức. Trong cuộc truy đuổi ngoạn mục diễn ra sau đó, Mike tìm ra được chiếc máy bay riêng của Cisco và rời khỏi Liberty City một cách tốt đẹp để đến Colombia làm lại từ đầu.

Nhân vật

Trò chơi có cốt truyện mới hoàn toàn. Nhân vật chính không còn là Claude nữa mà là một nhân vật mới mang tên Mike. Một số nhân vật từ bản Grand Theft Auto III còn xuất hiện trong game, bao gồm cả chủ tiệm bom 8-Ball và tên trùm Yakuza Asuka, mặc dù không có nhân vật Mafia Ý nào từ Grand Theft Auto III hiện diện trong game, và các nhân vật mới hoàn toàn như Vinnie (bạn của Mike và là ông chủ đầu tiên của người chơi), Cisco (lãnh đạo của Colombian Cartel), và Yuka (cô cháu gái của Asuka) đã được nhà sản xuất thêm vào. Một số nhân vật chỉ nhắc đến qua loa trong Grand Theft Auto III thì giờ đây được gặp mặt trực tiếp, chẳng hạn như King Courtney, ông trùm của băng Yardie.[3]